package 中等.滑动窗口;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个整数数组 nums 和一个整数 k 。
 * 一个元素 x 在数组中的 频率 指的是它在数组中的出现次数。
 * 如果一个数组中所有元素的频率都 小于等于 k ，那么我们称这个数组是 好 数组。
 * 请你返回 nums 中 最长好 子数组的长度。
 * 子数组 指的是一个数组中一段连续非空的元素序列。
 *
 * @ https://leetcode.cn/problems/length-of-longest-subarray-with-at-most-k-frequency/description/
 * @date 2024/07/17
 */
public class 最多K个重复元素的最长子数组_2958 {

    public static void main(String[] args) {

    }

    /**
     * 滑动窗口
     * 用哈希表记录元素出现的次数，右指针元素 a 次数超过 k 时，那么左指针
     * 往右移动，直到 a 元素次数 <= k
     */
    public int maxSubarrayLength(int[] nums, int k) {
        int ans = 0;
        Map<Integer, Integer> map = new HashMap<>();

        int left = 0, right = 0;
        while (right < nums.length) {

            int num = nums[right];
            map.put(num, map.getOrDefault(num, 0) + 1);
            right++;

            while (map.get(num) > k) {
                map.put(nums[left], map.get(nums[left]) - 1);
                left++;
            }
            ans = Math.max(ans, right - left);
        }

        return ans;
    }

}
